#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;

class Solution{
    private:
    vector<int> ans;

    public:
    // lower_bound
    // upper_bound

    //double ptr
    vector<int> ans1(vector<int>& nums, int target){
        int len = nums.size();
        int left = -1, right = -1;
        for(int i = 0; i < len; i++){
            if(nums[i] == target){
                right = left = i;
                while(right < len){
                    if(nums[right] == target){
                        right++;
                    }else{
                        i = right;
                        break;
                    }
                }
                right = right - 1;
            }
            if(right == len-1){
                break;
            }
        }

        vector<int> ret;
        ret.push_back(left);
        ret.push_back(right);

        return ret;
    }

    //二分法+递归
    vector<int> ans2(vector<int>& nums, int target){
        int len = nums.size();
        ans.push_back(-1);
        ans.push_back(-1);

        fun(nums, target, 0, len-1);
        return ans;
    }

    void fun(vector<int>& nums, int target, int left, int right){
        if(left > right){
            return;
        }
        int mid = left + (right - left) / 2;
        if(nums[mid] == target && ans[0] == -1){
            ans[0] = mid;
            ans[1] = mid;
        }else if(nums[mid] == target){
            ans[0] = min(mid, ans[0]);
            ans[1] = max(mid, ans[1]);
        }

        fun(nums, target, left, mid-1);
        fun(nums, target, mid+1, right);
    }


};

void test1(){
    Solution s;
    vector<int> nums = {5,7,7,8,8,10};
    int target = 8;
    
    // vector<int> ret = s.ans1(nums, target);
    vector<int> ret = s.ans2(nums, target);
    cout << "[" << ret[0] << ", " << ret[1] << "]" << endl;
}

void test2(){
    Solution s;
    vector<int> nums = {5,7,7,8,8,10};
    int target = 6;
    
    vector<int> ret = s.ans1(nums, target);
    cout << "[" << ret[0] << ", " << ret[1] << "]" << endl;
}

void test3(){
    Solution s;
    vector<int> nums = {1, 1};
    int target = 1;
    
    // vector<int> ret = s.ans1(nums, target);
    vector<int> ret = s.ans2(nums, target);
    cout << "[" << ret[0] << ", " << ret[1] << "]" << endl;
}

int main(void){
    test1();
    test2();
    test3();

    return 0;
}